from random import randint
import time

def quick_sort0(a):
    if len(a)<=0 :
        return []
    x=a[randint(0,len(a)-1)]
    rr=[]
    ll=[]
    mm=[]
    for i in a:
        if i<x :
            ll.append(i)
        elif i>x :
            rr.append(i)
        else :
            mm.append(i)
    return quick_sort(ll)+mm+quick_sort(rr)

def quick_sort(a,l,r):
    if l>=r:
        return
    i=l
    j=r
    # h=randint(l,r-1)
    h=(l+r)/2
    x=a[h]
    a[h]=a[i]
    while i<j :
        while i<j and a[j]>=x :
            j-=1
        # if i<j :
        a[i] = a[j]
        while i<j and a[i]<x :
            i+=1
        # if i<j :
        a[j]=a[i]
    a[i]=x
    quick_sort(a,l,i-1)
    quick_sort(a,i+1,r)

n = int(input())
d = []
for i in range(n):
    d.append(randint(0,n*n))

# print d0
print 'quick sort begin:'
print ' running...'

t1 = int(time.time()*1000)
quick_sort(d,0,n-1)
t2 = int(time.time()*1000)

print 'quick sort end.'


# print d1
p = True
for i in range(1,n):
    if d[i]<d[i-1]:
        p = False
        break

print ' the answer is '+('right'if p else 'wrong')+' !!!'
print ' run time : %dms'%(t2-t1)
